package Hashtable;
import java.util.*;

public class niuK_Work {

/* 两数之和
* 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。  */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        //遍历数组
        for (int i = 0; i < numbers.length; i++) {
            //将不包含target - numbers[i]，装入map中，包含的话直接返回下标
            if(map.containsKey(target - numbers[i]))
                return new int[]{map.get(target - numbers[i])+1, i+1};
            else
                map.put(numbers[i], i);
        }
        return null;
    }
    /*数组中出现次数超过一半的数字*/
    public int MoreThanHalfNum_Solution(int [] array) {
        int cond = -1;
        int cnt = 0;
        for (int i=0; i<array.length; ++i) {
            if (cnt == 0) {
                cond =array[i];
                ++cnt;
            }
            else {
                if (cond == array[i]) ++cnt;
                else --cnt;
            }

        }
        cnt = 0;
        for ( int k :array) {
            if (cond == k) ++cnt;
        }
        if (cnt > array.length / 2) return cond;
        return 0;
    }
    /*数组中只出现一次的两个数字*/
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
       int[] str=new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int k=array[i];
            if (map.containsKey(k)){
                map.put(k,map.get(k)+1);
            }else {
                map.put(k,1);
            }
        }
        int j=0;
        for (int i = 0; i < array.length; i++) {
            int k=array[i];
            if (map.get(k)==1){
               str[j]=k;
               j++;
            }
        }
        Arrays.sort(str);
        return str;
    }


    public int[] FindNumsAppearOnce2 (int[] array) {
        int res1 = 0;
        int res2 = 0;
        int temp = 0;
        //遍历数组得到a^b
        for(int i = 0; i < array.length; i++)
            temp ^= array[i];
        int k = 1;
        //找到两个数不相同的第一位
        while((k & temp) == 0)
            k <<= 1;
        for(int i = 0; i < array.length; i++){
            //遍历数组，对每个数分类
            if((k & array[i]) == 0)
                res1 ^= array[i];
            else
                res2 ^= array[i];
        }
        //整理次序
        if(res1 < res2)
            return new int[] {res1, res2};
        else
            return new int[] {res2, res1};
    }
    /*缺失的第一个正整数
    * 给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
    * 第一种方法:用哈希*/
    public int minNumberDisappeared1 (int[] nums) {
       HashMap<Integer,Integer> map =new HashMap<>();
        // write code here
        int count=1;
        for (int i = 0; i < nums.length; i++) {
            int k=nums[i];
           if (k>0&&!map.containsKey(k)){
               map.put(k,1);
           }
        }
        while (map.containsKey(count)){
            count++;
        }
        return count;
    }
   //天才的想法,原地哈希
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        //遍历数组
        for(int i = 0; i < n; i++)
            //负数全部记为n+1
            if(nums[i] <= 0)
                nums[i] = n + 1;
        for(int i = 0; i < n; i++)
            //对于1-n中的数字
            if(Math.abs(nums[i]) <= n)
                //这个数字的下标标记为负数
                nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]);
        for(int i = 0; i < n; i++)
            //找到第一个元素不为负数的下标
            if(nums[i] > 0)
                return i + 1;
        return n + 1;
    }
    /*三数之和
    * 给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。*/
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        int n = num.length;
        //不够三元组
        if(n < 3)
            return res;
        //排序
        Arrays.sort(num);
        for(int i = 0; i < n - 2; i++){
            if(i != 0 && num[i] == num[i - 1])
                continue;
            //后续的收尾双指针
            int left = i + 1;
            int right = n - 1;
            //设置当前数的负值为目标
            int target = -num[i];
            while(left < right){
                //双指针指向的二值相加为目标，则可以与num[i]组成0
                if(num[left] + num[right] == target){
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    while(left + 1 < right && num[left] == num[left + 1])
                        //去重
                        left++;
                    while(right - 1 > left && num[right] == num[right - 1])
                        //去重
                        right--;
                    //双指针向中间收缩
                    left++;
                    right--;
                }
                //双指针指向的二值相加大于目标，右指针向左
                else if(num[left] + num[right] > target)
                    right--;
                    //双指针指向的二值相加小于目标，左指针向右
                else
                    left++;
            }
        }
        return res;
    }
    /*BM55 没有重复项数字的全排列
    * 给出一组数字，返回该组数字的所有排列*/

        // 存所有排列的集合
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        public ArrayList<ArrayList<Integer>> permute(int[] num) {
            // 存一种排列
            LinkedList<Integer> list = new LinkedList<>();
            // 递归进行
            backTrack(num,list);
            return res;
        }

        public void backTrack(int[] num, LinkedList<Integer> list){
            // 当list中的长度等于数组的长度，则证明此时已经找到一种排列了
            if(list.size() == num.length){
                // add进返回结果集中
                res.add(new ArrayList<>(list));
                return;
            }
            // 遍历num数组
            for(int i = 0; i < num.length; i++){
                // 若当前位置中的数已经添加过了则跳过
                if(list.contains(num[i]))
                    continue;
                // 选择该数
                list.add(num[i]);
                // 继续寻找
                backTrack(num,list);
                // 撤销最后一个
                list.removeLast();
            }
        }
















}

